/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._279;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 * 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
 *
 * 示例 1:
 *
 * 输入: n = 12
 * 输出: 3
 * 解释: 12 = 4 + 4 + 4.
 * 示例 2:
 *
 * 输入: n = 13
 * 输出: 2
 * 解释: 13 = 4 + 9.
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._279
 * @ClassName: PerfectSquares
 * @Author: linyaonan
 * @Date: 2020/1/22 11:20
 */
public class PerfectSquares {
    int min = Integer.MAX_VALUE;
    public int numSquares(int n) {
        int maxAdd = getMaxAdd(n);
        List<Integer> add = new ArrayList<>();
        backTracing(add, n, maxAdd);
        return min;
    }

    private void backTracing(List<Integer>add, int t, int endKey) {
        if (add.size() > min) {
            return;
        }
        if (getListSum(add) == t) {
            min = Math.min(add.size(), min);
            return;
        }

        if (getListSum(add) > t) {
            return;
        }

        for (int key = endKey; key > 0; key--) {
            add.add(key * key);
            backTracing(add, t, key);
            add.remove(add.size() - 1);
        }
    }

    private long getListSum(List<Integer> add) {
        if (add == null) {
            return 0;
        }

        long s = 0L;
        for (Integer i : add) {
            s += i;
        }
        return s;
    }

    private int getMaxAdd(int n) {
        int getThisIndex = 0;
        for (long i = 46341L; i > 0; i--) {
            if (n >= i * i) {
                getThisIndex = (int) i;
                break;
            }
        }
        return getThisIndex;
    }

    public static void main(String[] args) {
        System.out.println(Integer.MAX_VALUE);
    }

    public int numSquares2(int n) {
        int[] dp = new int[n + 1]; // 默认初始化值都为0
        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 最坏的情况就是每次+1
            for (int j = 1; i - j * j >= 0; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程
            }
        }
        return dp[n];
    }

    /**
     * 可以看做完全背包问题，每一个数字可以用无数次，
     * i位置的数值如果平方大于目标n那么一定不能选就退化为从i-1个数值中组成正好等于n的选择策略
     * 如果i位置选择则变化为 从i个数值中组成正好等于n - i * i 的策略
     *
     * 递归做法，其中有很多步骤是重复的可以使用二维数组进行记忆优化
     *
     * @param n
     * @return
     */
    public int numSquares3(int n) {
        int i = (int) Math.sqrt(n);
        int[][] save = new int[n + 1][i + 1];
        // -1 表示没有计算过
        for (int[] row : save) {
            Arrays.fill(row, -1);
        }
        return getCount(n, i, save);

    }

    private int getCount(int n, int i, int[][] save) {
        if (save[n][i] != -1) {
            return save[n][i];
        }
        if (i == 0) {
            save[n][i] = n == 0 ? 0 : Integer.MAX_VALUE;
            return save[n][i];
        }
        if (i * i > n) {
            save[n][i] = getCount(n, i - 1, save);
            return save[n][i];
        }
        save[n][i] = Math.min(getCount(n - (i * i), i, save) + 1, getCount(n, i - 1, save));
        return save[n][i];
    }

    /**
     * 动态规划，完全01背包问题
     * i表示有多少组数值可以选择，1,2,3,4... t表示目标值
     * 状态转移方程：dp[i][t] = Math.min(dp[i-1][t], dp[i][t - i * i] + 1)，还有特殊情况当i * i > t 不能选择
     *
     * 题目中给出t的范围为0~10000 那么i的范围就是0 ~ 100
     * @param n
     * @return
     */
    public int numSquares4(int n) {
        int z = (int) Math.sqrt(n);
        int[][] dp = new int[z + 1][n + 1];
        Arrays.fill(dp[0], Integer.MAX_VALUE);
        dp[0][0] = 0;

        for (int i = 1; i * i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                if (j < i * i) {
                    // 选不了
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - i * i] + 1);
                }
            }
        }
        return dp[z][n];
    }

}
